#include <iostream>
using namespace std;
/**
 * Definition for singly-linked list.
 */
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (list1 && list2)
        {
            if (list2->val > list1->val)
            {
                cur->next = list1;
                list1 = list1->next;
            }
            else
            {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        cur = dummy->next;
        delete dummy;
        return cur;
    }
};

int main()
{
    ListNode *l11 = new ListNode(1);
    ListNode *l12 = new ListNode(2);
    ListNode *l13 = new ListNode(4);
    ListNode *l21 = new ListNode(1);
    ListNode *l22 = new ListNode(3);
    ListNode *l23 = new ListNode(4);
    l11->next = l12;
    l12->next = l13;
    l13->next = nullptr;
    l21->next = l22;
    l22->next = l23;
    l23->next = nullptr;
    ListNode *list1 = l11;
    ListNode *list2 = l21;
    Solution *sol;
    ListNode *res = sol->mergeTwoLists(list1, list2);
    while (res != nullptr)
    {
        printf("%d->", res->val);
        res = res->next;
    }
    delete l11, l12, l13, l21, l22, l23;
    return 0;
}